package com.ycsyxt.guide;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 递归：将复杂的问题，每次都解决一点点；
 * 并将剩下的任务转换成为更简单的问题等待下次求解，如此反复，直到最简单的形式；
 * @author ycs(15241496739 @ 163.com)
 * @date 2022/6/5
 **/
public class Class5 {
    public static List<List<Integer>> result = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    // 奖赏方式
    public static void getRewords(int start, int[] rewords, int total) {
        if (total < 0) {
            return;
        }
        if (total == 0) {
            result.add(new ArrayList<>(path));
        }

        for (int i = start; i < rewords.length; i++) {
            path.add(rewords[i]);
            getRewords(start + i, rewords, total - rewords[i]);
            path.remove(path.size() - 1);
        }
    }
    // 因式分解
    public static void getFactors(int number, int sum) {
        if (sum > number) {
            return;
        }
        if (sum == number) {
            result.add(new ArrayList<>(path));
        }

        for (int i = 2; i < number; i++) {
            path.add(i);
            getFactors(number, sum * i);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
//        int[] rewords = new int[]{1,2,5,10};
//        getRewords(0, rewords, 10);
//        result.forEach(System.out::println);
        getFactors(100, 1);
        List<List<Integer>> set = new ArrayList<>();
        Set<String> str = new HashSet<>();
        result.forEach(item -> {
            Integer[] integers = item.toArray(new Integer[0]);
            Arrays.sort(integers);
            StringBuffer sb = new StringBuffer();
            for (Integer integer: integers) {
                sb.append(integer).append(",");
            }
            if (!str.contains(sb.toString())) {
                set.add(item);
            }
            str.add(sb.toString());
        });
        set.forEach(System.out::println);
    }
}
